Sparse Table
Operations
Band (冪等半群) の列 $ (a_0, a_1, \dots, a_{n - 1}) を扱う．
空間計算量$ \Theta(n \log n)
$ \mathtt{build}(a_0, a_1, \dots, a_{n - 1})
与えられた列を表現する Sparse Table を作成する
時間計算量$ \Theta(n \log n)
$ \mathtt{fold}(l, r)
$ a_l \cdot a_{l + 1} \cdot \dots \cdot a_r を計算する
時間計算量$ \Theta(1)
Summary
https://gyazo.com/c98d7e72277e4226feeb808b781bcc1a
列のすべての区間を高々二つの区間で覆うように分割し，それぞれの区間の値を前計算しテーブルに保持する．
References
Notes
$ \mathtt{fold}の二項演算は結合律と冪等律を満たせば十分であり，この代数的構造は Band とよばれる．半束 (semilattice) と説明されることもあり，半束は Band に交換律を加えたものであるから十分条件としては正しいが，交換律は不要． $ (a b c) (b c d) = a ((b c) (b c)) d = a (b c) d = a b c dに注意
$ k \in [1, n] について$ \lg kが定数時間で (あるいは十分高速に) 求められる必要があるので，$ \mathtt{build}のときにすべての$ kについて前計算してテーブルを持っておくか，bit scan reverse を求められる組み込み関数 (__builtin_clz など) を用いる
テーブルの添字は, table[i][k]とtable[k][i]の2通りが考えられるが, 後者のほうがキャッシュが効いて早くなる
Implementations
Problems